<!DOCTYPE html>
<html lang="zh-cn">
<head>
    <title>引言, 计数原理, 鸽巢原理</title>
    <meta charset="utf-8" />
    <link rel="stylesheet" type="text/css" href="../../css/note.css" />
</head>
<body>

<p> 组合数学的两大分支是研究计数问题的<b>计数组合学</b>与研究最优组合的<b>极值组合学</b>, 我们这里主要涉及前者.
	在全部内容开始前, 假定读者具有集合与映射的基本概念.
</p>

<h2>引言: 十二重计数方法</h2>

<h3>集合元素的计数</h3>

<p class="definition">
	令 `X, Y` 为两个集合. 如果存在 `X` 到 `Y` 的一一对应 (即双射),
	则称 `X` 与 `Y` <b>对等</b>或<b>等势</b>.
</p>

<p class="definition">
	如果存在正整数 `n`, 使得集合 `X` 与集合
	`{1, 2, cdots, n}` 对等, 则称 `X` 为<b>有限集</b>,
	称 `X` 中<b>元素的个数</b>或 `X` 的<b>基数</b>为 `n`, 记为 `|X| = n`.
	我们也规定空集 `O/` 是有限集, 且 `|O/| = 0`.
	若 `X` 不是有限集, 则称它是<b>无限集</b>, 或者说, 它的元素有无穷多个.
</p>

<p class="remark">
	"集合中的元素个数" 的概念容易推广到无限集上, 即 "基数" 或 "势".
	这在数学分析, 实变函数等课程中均有涉及. 在组合数学中,
	我们将重点放在对有限集的讨论上.
</p>

<p class="definition">
	设 `X = {x_1, x_2, cdots, x_k}` 是一集合, `k ge 0`,
	`n_1, n_2, cdots, n_k` 是非负整数, 则称二元组的集合
	<span class="formula">
		`S = {(x_1, n_1), (x_2, n_2), cdots, (x_k, n_k)}`
	</span>
	为 `x_1, x_2, cdots, x_k` 的<b>多重集 (multiset)</b>, 记为
	<span class="formula">
		`S = {n_1 * x_1, n_2 * x_2, cdots, n_k * x_k}`
	</span>
	其中 `n_i` 称为元素 `x_i` 的<b>重数</b>, `i = 1, 2, cdots, k`.
	如果一个元素 `x_i` 的重数 `n_i = 0`, 我们认为 `x_i !in S`.
	因此我们认为下面两个多重集相等:
	<span class="formula">
		`{1 * a, 0 * b, 3 * c} = {1 * a, 3 * c}`
	</span>
	定义多重集的基数为
	<span class="formula">
		`|S| = sum_(i=1)^k n_i`.
	</span>
</p>

<p class="remark">
	多重集合的一个例子是多项式的根, 每个根的重数对应于在多重集中的重数.
</p>

<p>	我们把计算集合 (多重集) 中元素个数的问题统称为<b>计数问题</b>.
</p>

<h3>十二重计数方法</h3>

<p>	在计数时, 尤其需要关注的问题是<b>在什么意义下计数</b>,
	换言之, 设 `x_1, x_2 in X`, `x_1` 与 `x_2` 什么情况下被视为相等的?
	这是计数的关键问题.
	我们将看到, 在不同意义下, 看起来相似的计数问题有完全不同的结果,
	其解答的难度与算法的复杂度也各不相同.
</p>

<p>	现在考虑如下一般的计数问题,
	称为<b>十二重计数方法 (twelvefold way)</b>.
	它几乎涵盖了全部典型的计数问题,
	有大量的实际问题背景, 我们将在具体讨论每一情形时举例说明.
</p>

<ol class="question" id="que-twelvefold-way">
	设 `X, Y` 为有限集合, `|X| = m`, `|Y| = n`,
	`F` 是全体 `X` 到 `Y` 上的映射 `f` 的集合,
	`I sube F` 是 `F` 中的单射 (injection) 形成的子集,
	`S sube F` 是 `F` 中的满射 (surjection) 形成的子集.
	在以下 4 种意义下对 `F`, `I`, `S` 的元素进行计数:
	<li><b>通常意义</b>.
		采用映射相等的定义. 两个映射 `f_1, f_2 in F`
		相等当且仅当它们把 `X` 中任意元素映到相同的像, 即
		<span class="formula">
			`(AA x in X)` `f_1(x) = f_2(x)`.
		</span>
	</li>
	<li><b>相差一个 `X` 上的排列的意义</b>.
		对 `X` 的元素不加区分, 映射 `f_1, f_2 in F` 相等当且仅当 `Y`
		中的各个元素在 `f_1` 和 `f_2` 下有相等数目的原像, 即
		<span class="formula">
			`(AA y in Y)` `|f_1^-1(y)| = |f_2^-1(y)|`.
		</span>
		这类问题计数了<b>多重集合的子集</b>.
	</li>
	<li><b>相差一个 `Y` 上的排列的意义</b>.
		对 `Y` 的元素不加区分. 映射 `f_1, f_2 in F` 相等当且仅当
		<span class="formula">
			`"Ker" f_1 = "Ker" f_2`.
		</span>
		其中 `"Ker" f = {(x_1, x_2) in X xx X: f(x_1) = f(x_2)}`.
		这类问题计算<b>集合的分划数</b>.
	</li>
	<li><b>相差 `X` 与 `Y` 上的排列的意义</b>.
		对 `X` 的元素不加区分, 对 `Y` 的元素也不加区分. 映射 `f_1, f_2 in
		F` 相等当且仅当下面的多重集合相等
		<span class="formula">
			`{|f_1^-1(y)|: y in Y} = {|f_2^-1(y)|: y in Y}`.
		</span>
		这类问题计算<b>非负整数的分拆数</b>.
	</li>
	3 个集合在 4 种意义下共形成 12 个计数问题, 用集合表示,
	分别记为 `F_1 ~ F_4, I_1 ~ I_4, S_1 ~ S_4`, 见下表.
</ol>

<table>
	<tr>
		<td></td>
		<td>`f` 是普通映射</td>
		<td>`f` 是单射</td>
		<td>`f` 是满射</td>
	</tr>
	<tr>
		<td>在通常意义下</td>
		<td>`F_1`</td>
		<td>`I_1`</td>
		<td>`S_1`</td>
	</tr>
	<tr>
		<td>在相差一个 `X` 上的排列的意义下</td>
		<td>`F_2`</td>
		<td>`I_2`</td>
		<td>`S_2`</td>
	</tr>
	<tr>
		<td>在相差一个 `Y` 上的排列的意义下</td>
		<td>`F_3`</td>
		<td>`I_3`</td>
		<td>`S_3`</td>
	</tr>
	<tr>
		<td>在相差 `X` 与 `Y` 上的排列的意义下</td>
		<td>`F_4`</td>
		<td>`I_4`</td>
		<td>`S_4`</td>
	</tr>
</table>

<div class="remark">
	现在用物体与盒子的语言来重新叙述上面的计数问题.
<p>	假设有 `m` 件物体, `n` 个盒子, 现要计数将这些物体放入这些盒子的方法数.
	容易看出物体-盒子语言与映射语言的对应关系: 如
	`f(x)` 表示放有物体 `x` 的盒子;
	`f_1(x) = f_2(x)` 表示两种方法将物体 `x` 放进了同一个盒子;
	`f^-1(y)` 表示盒子 `y` 中的所有物体; 等等.
	根据放入盒子时的限制条件
	(不作要求/每个盒子的物体不超过一件/每个盒子不空)
	和对物体与盒子是否标号 (labeled/unlabeled) (换言之, 是否作区分
	(distinct)),
	亦引出十二种不同的计数问题. 我们不作证明地在下表中给出答案.
</p>
<table>
	<tr>
		<td></td>
		<td>不作要求</td>
		<td>每个盒子的物体不超过一件</td>
		<td>每个盒子不空</td>
	</tr>
	<tr>
		<td>对物体与盒子都作区分</td>
		<td>`n^m`</td>
		<td>`[n]_m`</td>
		<td>`n! S(m, n)`</td>
	</tr>
	<tr>
		<td>对物体不作区分</td>
		<td>`(m+n-1;m) = (-n; m) (-1)^m`</td>
		<td>`(n;m)`</td>
		<td>`(m-1;n-1)`</td>
	</tr>
	<tr>
		<td>对盒子不作区分</td>
		<td>`sum_(i=1)^n S(m, i)`</td>
		<td>`[m le n]`</td>
		<td>`S(m, n)`</td>
	</tr>
	<tr>
		<td>对物体与盒子都不作区分</td>
		<td>`sum_(i=1)^n p_i(m)`</td>
		<td>`[m le n]`</td>
		<td>`p_n(m)`</td>
	</tr>
</table>
<ol>
	其中
	<li>`[n]_m = P(n, m)` `= n(n-1) cdots (n-m+1)` 是 `n` 选 `m`
		的排列数.
	</li>
	<li>`(n;m) = C(n, m) = [n]_m//m!` 是 `n` 选 `m` 的组合数.</li>
	<li>`S(m, n) = {m;n}`
		`= 1/(n!) sum_(i=0)^n (n;i) (-1)^i (n-i)^m`
		是第二类 Stirling 数.</li>
	<li>`p_n(m)` 是将整数 `m` 分拆成 `n` 部分的分拆数.</li>
	<li>`[m le n] = {1, if m le n","; 0, if "else".:}`</li>
</ol>
</div>

<h2>计数原理</h2>

<h2>鸽巢原理</h2>

<p>	鸽巢原理又名抽屉原理或 Dirichlet 原理,
	概念直白浅显, 但是应用广泛, 形式灵活, 是组合数学和数论中常用的工具.
</p>

<ol class="theorem">
	<b>鸽巢原理</b> 令 `n in ZZ^+`,
	<li>将 `n+1` 个物体放入 `n` 个盒子, 不论怎么放,
		至少有一个盒子中的物体多于一个;
	</li>
	<li>将 `n-1` 个物体放入 `n` 个盒子, 不论怎么放,
		至少有一个盒子是空的.
	</li>
</ol>

<ol class="proof">
	<li>若每个盒子中的物体数目不多于一个, 则物体总数至多为 `n`, 引出矛盾;
	</li>
	<li>若每个盒子中的物体数目不少于一个, 则物体总数至少为 `n`, 引出矛盾.
	</li>
</ol>

<p class="example">
	同年出生的 400 人中至少有两人同一天生日.
</p>

<p class="corollary">
	设有物体若干, 它们可以分成 `n` 类.
	从中选 `n+1` 个物体, 必有两个物体属于同类.
</p>

<p class="proof">
	做 `n` 个盒子, 将同类物体放在同一个盒子中.
	这样一来, 被选中的 `n+1` 个物体也被放进了盒子.
	由鸽巢原理, 被选中的物体中至少有两个被放入同一个盒子,
</p>

<p class="example">
	从 `n` 双手套中任取 `n+1` 只, 至少能配成一双手套.
</p>

<ol class="theorem">
	<b>推广的鸽巢原理</b>
	<li>将 `mn + 1` 个物体放入 `n` 个盒子,
		则至少有一个盒子中的物体数目多于 `m` 个;
	</li>
	<li>将 `mn - 1` 个物体放入 `n` 个盒子,
		则至少有一个盒子中的物体数目少于 `m` 个.
	</li>
	证明方法类似.
</ol>

<p class="example">
	将五条线段用红色或蓝色着色, 一定有三条线段颜色相同 (取 `m = n = 2`).
</p>

<p class="corollary">
	将 `mn` 个物体放入 `n` 个盒子, 则至少有一个盒子中的物体数目不少于 `m`
	个, 至少有一个盒子中的物体数目不多于 `m` 个.
</p>

<p class="proof">
	若再放入一个物体, 由推广的鸽巢原理, 有一个盒子中的物体数目多于 `m` 个,
	说明它原先不少于 `m` 个;
	若少放入一个物体, 由推广的鸽巢原理, 有一个盒子中的物体数目少于 `m` 个,
	说明它原先不多于 `m` 个.
</p>

<p class="example">
	将正方体的每个面涂成红色或蓝色中的一种, 一定有三个面颜色相同 (取 `m =
	3, n = 2`).
</p>

<p class="theorem">
	<b>一般的鸽巢原理</b>
	将 `m` 个物体放入 `n` 个盒子,
	则至少有一个盒子中的物体数目不少于 `|__ (m-1)/n __|+1` 个,
	至少有一个盒子中的物体数目不多于 `|~ (m+1)/n ~|-1` 个.
</p>

<p class="remark">
	鸽巢原理有它的非离散版本, 如: 三角形至少有一内角不小于 60 度.
</p>

<h3>鸽巢原理的应用</h3>

<p>	鸽巢原理可以用于一些存在性问题的证明.
	运用鸽巢原理时, 要善于构造具有特定属性的盒子.
</p>

<p class="example">
	`n` 个人参加聚会, 他们中有一些人相互握了手 (和自己握手不算).
	一定有两个人握手次数相同.
</p>

<p class="proof">
	如果在聚会上, 每个人都至少握了一次手, 那么全部可能的握手次数是
	`1, 2, cdots, n-1`;
	如果有的人没有握过手, 全部可能的握手次数则是
	`0, 1, cdots, n-2`.
	不论哪一种情形, 可能的握手次数只有 `n-1` 种.
	由鸽巢原理, 一定有两个人握手次数相同.
</p>

<p class="example">
	从 `1, 2, cdots, 15` 中任取 9 个数, 其中必有两个数之和是 17.
</p>

<p class="proof">
	将全部 15 个数放入 8 个集合: `{1}, {2, 15}, {3, 14}, cdots, {8, 9}`.
	由鸽巢原理, 所选的 9 个数中至少有两个属于同一集合. 它们的和就是 17.
</p>

<p class="example">
	从 `1, 2, cdots, 100` 中任取 51 个数, 必有两个数,
	其中一个是另一个的倍数.
</p>

<p class="proof">
  每个正整数都能写成 奇数`* 2^n` 的形式, 但所有可能的奇数只有 50 个:
  `1, 3, cdots, 99`. 因此必有两个正整数对应于同一个奇数, 设它们是
  `a * 2^n`, `a * 2^m`, 显然一个是另一个的倍数.
</p>

<ol class="example">
	<b>同色三角形问题</b>
	<li>设空间中有 6 个点, 任意三点不共线.
		现将每两点用红色或蓝色的线段连接, 则必存在一个三边同色的三角形.
		这个问题的一个等价表述是: 在任意 6 人的集会上, 或者有 3
		个人以前彼此相识, 或者有 3 个人以前彼此不相识.
	</li>
	<li>设空间中有 17 个点, 任意三点不共线.
		用 3 种颜色给所有连接这些点的线段着色,
		则必存在一个三边同色的三角形.
	</li>
</ol>

<ol class="proof">
	<li>任取其中一点, 由这点出发的 5 条线段中, 至少有 3 条同色,
		假定是红色.  把这三条线段记为 `OA, OB, OC`, 考察三角形 `ABC`.
		若三角形 `ABC` 其中一边是红色, 如 `AB` 是红色, 则三角形 `OAB`
		的三边都是红色, 是同色三角形; 否则三角形 `ABC` 的三边都是蓝色,
		是同色三角形.
	</li>
	<li>取其中一点 `A`, 由这点出发的 16 条线段中, 至少有 6 条同色,
		设它们具有颜色 `a`.  考虑这 6 条线段异于 `A` 的 6 个端点.
		如果它们之间有一条连线具有颜色 `a`, 则同色三角形已经找到; 否则, 这
		6 个点之间的连线只由另外两种颜色着色, 由 1 知必存在同色三角形.
	</li>
</ol>

<h3>鸽巢原理的映射表述</h3>

<p class="definition">
	设集合 `X, Y != O/`.  考虑从 `X` 到 `Y` 的对应法则 `f`,
	如果对任意 `x in X`, 根据法则 `f` 都<b>存在唯一</b>的 `y in Y`
	与之对应, 则称 `f` 为 `X` 到 `Y` 的一个<b>映射</b>, 记为 `f: X to Y`.
	`y` 称为 `x` 在 `f` 下的<b>像</b>, 记为 `y = f(x)`.
</p>

<p class="definition">
	设 `f: X to Y`. 对 `y in Y`, 称集合
	<span class="formula">
		`f^-1(y) = {x in X: f(x) = y}`
	</span>
	为 `y` 关于映射 `f` 的<b>原像集</b>.
</p>

<ol class="definition">
	设映射 `f: X to Y`.
	<li>如果由 `f(x_1) = f(x_2)` 能推出 `x_1 = x_2`,
		则称 `f` 是<b>单射</b>;
		显然 `f` 是单射当且仅当对任意 `y in Y`, `|f^-1(y)| le 1`;
	</li>
	<li>如果对任意 `y in Y`, 都存在 `x in X`, 使得 `y = f(x)`,
		则称 `f` 是<b>满射</b>;
		显然 `f` 是满射当且仅当对任意 `y in Y`, `|f^-1(y)| ge 1`;
	</li>
	<li>如果 `f` 既是单射又是满射, 则称 `f` 是<b>双射</b>;
		显然 `f` 是双射当且仅当对任意 `y in Y`, `|f^-1(y)| = 1`.
		<!--
		这时由 `y in Y` 唯一确定了元素 `x in X: f(x) = y`,
		把这一对应关系记为 `f^-1`. `f^-1` 是一个映射,
		称为 `f` 的<b>逆</b>.
		-->
	</li>
</ol>

<p class="theorem" id="the-isb-map-exist">
	<b>鸽巢原理</b>
	设 `X, Y != O/` 为有限集,
	则存在 `X to Y` 的单射的充要条件是 `|X| le |Y|`,
	存在 `X to Y` 的满射的充要条件是 `|X| ge |Y|`;
	因此, 存在 `X to Y` 的双射的充要条件是 `|X| = |Y|`.
</p>

<p class="proof">
	我们只证明单射的情形, 满射的证明类似.
	设 `X = {x_1, x_2, cdots, x_m}`, `Y = {y_1, y_2, cdots, y_n}`,
	则 `|X| = m`, `|Y| = n`.
	<br/>
	充分性: 当 `m le n` 时, 显然 `f(x_i) = y_i`, `i = 1, 2, cdots, m`
	是 `X` 到 `Y` 的单射.
	<br/>
	必要性: 若 `f: X to Y` 是单射, 对每个 `y_i in Y`,
	考虑原像集 `f^-1(y_i)`, 有 `|f^-1(y_i)| le 1`.
	注意到 `X` 是各 `f^-1(y_i)` 的不交并, 由加法原理,
	<span class="formula">
		` |X|
		= |uuu_(i=1)^n f^-1(y_i)|
		= sum_(i=1)^n |f^-1(y_i)|
		le n`.
	</span>
</p>

<p class="definition">
	设映射 `f: X to Y`. 若 `X_1 sube X`, 定义映射
	<span class="formula">
		`f|_(X_1): X_1 to Y`<br/>
		`x to f(x)`.
	</span>
	称为 `f` 在子集 `X_1` 上的<b>限制</b>.
</p>

<p class="theorem">
	设 `X, Y != O/` 为有限集, 且 `|X| = |Y|`. 若 `f: X to Y`, 则
	`f` 是单射当且仅当 `f` 是满射, 从而当且仅当 `f` 是双射.
</p>

<ol class="proof">
	<li>设 `f` 不是满射,
		由定义, 存在 `y in Y`, 对任意 `x in X`, `f(x) != y`.
		所以 `f` 也是从 `X` 到 `Y\\{y}` 的映射.
		但 `|Y\\{y}| lt |Y| = |X|`, 所以由<a class="ref"
			href="#the-isb-map-exist"></a>, `f` 不是单射.
	</li>
	<li>设 `f` 不是单射, 则存在 `x_1, x_2 in X`, `x_1 != x_2`,
		`f(x_1) = f(x_2)`.
		所以 `f` 限制在 `X\\{x_1}` 上是 `X\\{x_1}` 到 `Y` 的映射.
		但 `|X\\{x_1}| lt |X| = |Y|`,
		所以由<a class="ref" href="#the-isb-map-exist"></a>,
		`f` 限制在 `X\\{x_1}` 上不是满射,
		即存在 `y in Y`, 对任意 `x in X\\{x_1}`, `f(x) != y`.
		因为 `x_2 in X\\{x_1}`,
		所以 `f(x_1) = f(x_2) != y`.
		因而 `f` 不是满射.
	</li>
</ol>

<p>	现在我们可以解决引言中 `I_3, I_4` 的计数问题.
	`I_3` 表示 `X` 所有可能的分划, 且每一类中只含不超过一个元素.
	`I_4` 表示数字 `|X|` 的分拆, 每一部分不超过 1.
	显然这样的分划 (分拆) 都只有一种取法 (如果它存在),
	因此二者的结论都是平凡的.
	由鸽巢原理, `I_3` (或 `I_4`) 非空当且仅当 `m le n`, 所以
	<span class="formula">
		`|I_3| = |I_4| = {1, if m le n","; 0, if "else.":}`
	</span>
</p>

<script src="../../js/note.js?type=math"></script>
</body>
</html>
